package top.humbleyuan.dp;

import java.util.Arrays;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 21:12
 * @Des 不同路径
 */
public class LeetCode_62 {
    public static void main(String[] args) {
        // 一般dp
        m1();

        // 简化dp
        m2();
    }

    public static void m1() {
        // 网格大小
        int m = 7,n = 3;
        int[][] d = new int[n][m];

        d[0][0] = 1;
        for (int i = 0;i < n;i++) {
            for(int j = 0; j < m;j++) {
                if(i == 0 && j == 0)
                    continue;
                d[i][j] = (i==0 ? 0 : d[i-1][j]) + (j==0 ? 0 : d[i][j-1]);
            }
        }

        System.out.println("共有：" + d[n-1][m-1] + "条路径");
    }

    /**
     * 用一个一维数组:
     * 一行一行求：
     * 1.因为二维数组的话第一行和第一列都为1，可先设为一
     * 2.从第二行开始，因为cur记录着上一行的数据，那么现在这一行的cur[j] = cur[j](上一个) + cur[j-1](前一个已经变成新一行的数据)
     */
    public static void m2() {
        // 网格大小
        int m = 7,n = 3;

        int[] d = new int[m];
        Arrays.fill(d,1);
        for(int i = 1;i < n;i++) {
            for (int j = 1;j < m;j++) {
                d[j] = d[j] + d[j-1];
            }
        }
        System.out.println(d[m-1]);
    }
}
